package leetcode.LinkedList;

/**
 * @author MaoLin Wang
 * @date 2020/2/1111:28
 */
public class _142DetectCycle {
    //题解：https://leetcode-cn.com/problems/linked-list-cycle-ii/solution/linked-list-cycle-ii-kuai-man-zhi-zhen-shuang-zhi-/
    public  static ListNode detectCycle(ListNode head) {
        if (head==null){
            return null;
        }
        ListNode slow = head;
        ListNode fast = head;
        boolean flag=false;
        while (fast != null && fast.next != null) {

            slow = slow.next;
            fast = fast.next.next;
            if (slow==fast) {
                flag=true;
               break;
            }
        }
        if (!flag){
            return null;
        }
        /*
             1，f=2s  快指针走的步数是慢指针的两杯
             2. f=s+nb  两个指针相遇时，快指针比慢指针多走 n 圈，一圈长度为 b
             3. 所以 s = nb , f = 2nb   可以理解为，此时 fast 走了 2n 圈，slow 走了 n 圈，n 未知
             此时让快指针从新回到 head 节点，slow 在原处，假设从 head 到环入口长度为 a，且每走一圈会再次回到入口，
             则每次走到入口的步数 k = a + nb
             而此时 slow 已经走了 nb，因此只需要走 a 步就可以到入口，那么让在 head 未知的 fast 和 slow 同时走 a 步，相遇的节点就是环入口
         */
        ListNode result=head;
        while (result!=slow){
            result=result.next;
            slow=slow.next;
        }
        return result;

    }

    public ListNode detectCycle2(ListNode head) {
        if (head == null){
            return  null;
        }
        ListNode slow=head;
        ListNode fast=head;
        boolean meet=false;
        while (fast!=null && fast.next!=null){
            fast=fast.next.next;
            slow=slow.next;
            if (slow == fast){
                meet=true;
                break;
            }
        }
        if (!meet){
            return null;
        }
        slow= head;
        while (slow!=fast){
            slow=slow.next;
            fast=fast.next;
        }
        return slow;
    }

    public static void main(String[] args) {
        ListNode l1=new ListNode(1);
        ListNode node1 = l1.next = new ListNode(2);
        l1.next.next=new ListNode(3);
        l1.next.next.next=new ListNode(4);
        ListNode node = l1.next.next.next.next = new ListNode(5);
        node.next=node1;

        ListNode node2 = detectCycle(l1);
        System.out.println(node2+"a");
    }
}
